<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Detecting a small subset of infeasible linear inequalities</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/sparse_heuristics/html/sparse_infeas_dual.html">
<link rel="stylesheet" href="../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Detecting a small subset of infeasible linear inequalities</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Section 5.8, Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Written for CVX by Almir Mutapcic - 02/18/06</span>
<span class="comment">%</span>
<span class="comment">% We consider a set of linear inequalities A*x &lt;= b which are</span>
<span class="comment">% infeasible. Here A is a matrix in R^(m-by-n) and b belongs</span>
<span class="comment">% to R^m. We apply a l1-norm heuristic to find a small subset</span>
<span class="comment">% of mutually infeasible inequalities from a larger set of</span>
<span class="comment">% infeasible inequalities. The heuristic finds a sparse solution</span>
<span class="comment">% to the alternative inequality system.</span>
<span class="comment">%</span>
<span class="comment">% Original system is A*x &lt;= b and it alternative ineq. system is:</span>
<span class="comment">%</span>
<span class="comment">%   lambda &gt;= 0,   A'*lambda == 0.   b'*lambda &lt; 0</span>
<span class="comment">%</span>
<span class="comment">% where lambda in R^m. We apply the l1-norm heuristic:</span>
<span class="comment">%</span>
<span class="comment">%   minimize   sum( lambda )</span>
<span class="comment">%       s.t.   A'*lambda == 0</span>
<span class="comment">%              b'*lambda == -1</span>
<span class="comment">%              lambda &gt;= 0</span>
<span class="comment">%</span>
<span class="comment">% Positive lambdas gives us a small subset of inequalities from</span>
<span class="comment">% the original set which are mutually inconsistent.</span>

<span class="comment">% problem dimensions (m inequalities in n-dimensional space)</span>
m = 150;
n = 10;

<span class="comment">% fix random number generator so we can repeat the experiment</span>
seed = 0;
randn(<span class="string">'state'</span>,seed);

<span class="comment">% construct infeasible inequalities</span>
A = randn(m,n);
b = randn(m,1);

fprintf(1, [<span class="string">'Starting with an infeasible set of %d inequalities '</span> <span class="keyword">...</span>
            <span class="string">'in %d variables.\n'</span>],m,n);

<span class="comment">% you can verify that the set is infeasible</span>
<span class="comment">% cvx_begin</span>
<span class="comment">%   variable x(n)</span>
<span class="comment">%   A*x &lt;= b;</span>
<span class="comment">% cvx_end</span>

<span class="comment">% solve the l1-norm heuristic problem applied to the alternative system</span>
cvx_begin
   variables <span class="string">lambda(m)</span>
   minimize( sum( lambda ) )
   subject <span class="string">to</span>
     A'*lambda == 0;
     b'*lambda == -1;
     lambda &gt;= 0;
cvx_end

<span class="comment">% report the smaller set of mutually inconsistent inequalities</span>
infeas_set = find( abs(b.*lambda) &gt; sqrt(eps)/n );
disp(<span class="string">' '</span>);
fprintf(1,<span class="string">'Found a smaller set of %d mutually inconsistent inequalities.\n'</span>,<span class="keyword">...</span>
        length(infeas_set));
disp(<span class="string">' '</span>);
disp(<span class="string">'A smaller set of mutually inconsistent inequalities are the ones'</span>);
disp(<span class="string">'with row indices:'</span>), infeas_set'

<span class="comment">% check that this set is infeasible</span>
<span class="comment">% cvx_begin</span>
<span class="comment">%    variable x_infeas(n)</span>
<span class="comment">%    A(infeas_set,:)*x_infeas &lt;= b(infeas_set);</span>
<span class="comment">% cvx_end</span>
</pre>
<a id="output"></a>
<pre class="codeoutput">
Starting with an infeasible set of 150 inequalities in 10 variables.
 
Calling sedumi: 150 variables, 11 equality constraints
------------------------------------------------------------
SeDuMi 1.21 by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 11, order n = 151, dim = 151, blocks = 1
nnz(A) = 1650 + 0, nnz(ADA) = 121, nnz(L) = 66
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            2.27E+02 0.000
  1 :   1.27E-02 7.71E+00 0.000 0.0339 0.9900 0.9900   2.93  1  1  1.7E+00
  2 :   4.31E-01 2.34E+00 0.000 0.3028 0.9000 0.9000   0.88  1  1  8.0E-01
  3 :   5.11E-01 1.16E+00 0.000 0.4971 0.9000 0.9000   0.88  1  1  5.3E-01
  4 :   5.53E-01 4.79E-01 0.000 0.4126 0.9000 0.9000   0.95  1  1  2.9E-01
  5 :   5.86E-01 1.85E-01 0.000 0.3860 0.9000 0.9000   0.95  1  1  1.4E-01
  6 :   5.96E-01 7.30E-02 0.000 0.3946 0.9000 0.9125   0.99  1  1  6.2E-02
  7 :   5.99E-01 2.74E-02 0.000 0.3748 0.9000 0.9202   1.00  1  1  2.6E-02
  8 :   6.01E-01 7.80E-03 0.000 0.2850 0.9105 0.9000   1.00  1  1  7.4E-03
  9 :   6.01E-01 4.39E-04 0.000 0.0563 0.9902 0.9900   1.00  1  1  4.2E-04
 10 :   6.01E-01 5.09E-07 0.000 0.0012 0.9990 0.9990   1.00  1  1  
iter seconds digits       c*x               b*y
 10      0.0   Inf  6.0131198034e-01  6.0131198034e-01
|Ax-b| =   7.1e-17, [Ay-c]_+ =   1.3E-16, |x|=  2.8e-01, |y|=  8.1e-01

Detailed timing (sec)
   Pre          IPM          Post
0.000E+00    4.000E-02    0.000E+00    
Max-norms: ||b||=1, ||c|| = 1,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 9.91492.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.601312
 
Found a smaller set of 11 mutually inconsistent inequalities.
 
A smaller set of mutually inconsistent inequalities are the ones
with row indices:

ans =

     1    22    33    54    59    73    79    94   115   136   149

</pre>
</div>
</body>
</html>